package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * a03_组合优化
 * </p>
 *
 * @author flyduck
 * @since 2024-12-29
 */
public class a03_组合优化 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        LinkedList<Integer> result = new LinkedList<>();

        traversal(resultList,result,n,k,1);
        return resultList;
    }

    public void traversal(List<List<Integer>> resultList,
                          LinkedList<Integer> result,
                          int n,
                          int k,
                          int startIdx){
        if (result.size() == k){
            resultList.add(new ArrayList<>(result));
            return;
        }

        //1,2,3,4,5,6,7,8,9,10
        //我已经选取了3个了，总共要5个
        //从1开始可以
        //从2开始可以
        //...
        //从8开始可以  10 - (5 - 2) + 1 = 8

        //k - result.size()：还需要选取的元素的个数
        //还需要选取的元素的个数至多要从哪里开始：n - (k - result.size()) + 1
        for (int i = startIdx; i <= n - (k - result.size()) + 1; i++) {
            result.add(i);
            traversal(resultList, result, n, k, i + 1);
            result.removeLast();
        }

    }
}
